// 连续数组
class Solution
{
public:
    int findMaxLength(vector<int>& nums)
    {
        // 1、建表 && 初始化
        unordered_map<int, int> hash;
        hash[0] = -1;
        // 2、前缀和 + 哈希表
        int sum = 0, maxLength = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            sum += (nums[i] == 0 ? -1 : 1); //计算当前位置的前缀和
            if(hash.count(sum)) maxLength = max(maxLength, i - hash[sum]); //更新结果
            else hash[sum] = i; //更新哈希表
        }
        // 3、返回值
        return maxLength;
    }
};

// 矩阵区域和
class Solution
{
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
    {
        int m = mat.size(), n = mat[0].size();
        // 1、预处理一个矩阵和数组
        vector<vector<int>> sum(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; ++i)
            for(int j = 1; j <= n; ++j)
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];

        // 2、求矩阵区域和
        vector<vector<int>> ans(m, vector<int>(n));
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
            {
                // 计算矩阵左上角和右下角下标
                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
                // 计算区域元素之和
                ans[i][j] = sum[x2][y2] - (sum[x1 - 1][y2] + sum[x2][y1 - 1]) + sum[x1 - 1][y1 - 1];
            }

        // 3、返回值
        return ans;
    }
};